Triangle Evolution-A Hybrid Heuristic for Global Optimization

Abstract This paper presents a hybrid heuristic{triangle evolution (TE) for global optimization. It is a real coded evolutionary algorithm. As in di®erential evolution (DE), TE targets each individual in current population and attempts to replace it by a new better individual. However, the way of generating new individuals is di®erent. TE generates new individuals in a Nelder- Mead way, while the simplices used in TE is 1 or 2 dimensional. The proposed algorithm is very easy to use and e±cient for global optimization problems with continuous variables. Moreover, it requires only one (explicit) control parameter. Numerical results show that the new algorithm is comparable with DE for low dimensional problems but it outperforms DE for high dimensional problems.

reducing symmetries to generate easier sat instances

Finding countermodels is an effective way of disproving false conjectures. In first-order predicate logic, model finding is an undecidable problem. But if a finite model exists, it can be found by exhaustive search. The finite model generation problem in the first-order logic can also be translated to the satisfiability problem in the propositional logic. But a direct translation may not be very efficient. This paper discusses how to take the symmetries into account so as to make the resulting problem easier. A static method for adding constraints is presented, which can be thought of as an approximation of the least number heuristic (LNH). Also described is a dynamic method, which asks a model searcher like SEM to generate a set of partial models, and then gives each partial model to a propositional prover. The two methods are analyzed, and compared with each other.

可满足性问题研究

数理逻辑是计算机科学的基础，而逻辑公式的可满足性问题是计算机科学和人工智能领域中的一个著名而又重要的问题。它在计算机科学和人工智能研究中有广泛的应用。本文将重点介绍实际可用的判定算法及其相关技术。 本文的研究分两大方向，分别是命题逻辑的可满足性问题研究和一阶逻辑的可满足性问题研究。命题逻辑的可满足性问题（Satisfiability Problem）是一个历史悠久的问题，一般简称为 SAT问题。SAT 问题的求解算法有两大类，分别是确定性算法和非确定性算法。本文只研究确定性算法的相关内容，尤其是如何进行剪枝。我们充分调研了SAT求解算法和求解工具的相关知识，在此基础上，提出了local Lemma 这个剪枝技术，该技术可以更加充分地挖掘剪枝信息，达到进行更多剪枝的目的。 在一阶逻辑的可满足性问题研究方面，本文采取直接搜索可行的一阶逻辑模型的方法研究有限论域上的一阶逻辑的可满足性问题。该方法本质上就是深度优先的回溯搜索。因此，我们的研究重点就是如何找到问题的更高效的一阶逻辑的表示以及如何采用启发式的方式进行剪枝。在这个问题上，我的主要工作有两个：一个是模型搜索中适用于谓词的同构消去技术，包括Row by Row策略和Ramsey Number 策略两个技术；另一个是 DASH（Decision Assignment Scheme Heuristic），用来在生成有限模型的时候边搜索边消除同构子空间。DASH 能用近乎零代价保证输出的模型都是互不同构的。这两个技术都是基于有限论域中的元素的固有对称性，换言之，就是需要有限论域中的元素是两两可交换的。 在已有的成果的基础上，我们又尝试使用它们去求解一些数学中的实际问题，如拟群拉丁方，有限射影平面，正交拉丁方（组）等。我们给出了在这几个方面的一些尝试和初步结果，包括一个重要的定理和若干效率提高了几个数量级的改进。 值得一提的是，和马菲菲共同提出的横截矩阵（Transversal Matrix）概念是一个新颖的成果，使得正交拉丁方的表示和求解取得了明显的改进。在这个概念的基础上，进一步给出了几个定理，进行了理论上的拓展。实验数据表明，我们的求解途径和技术能有效解决拉丁方相关的问题。

constructing finite algebras with falcon

The generation of models and counterexamples is an important form of reasoning. In this paper, we give a formal account of a system, called FALCON, for constructing finite algebras from given equational axioms. The abstract algorithms, as well as some implementation details and sample applications, are presented. The generation of finite models is viewed as a constraint satisfaction problem, with ground instances of the axioms as constraints. One feature of the system is that it employs a very simple technique, called the least number heuristic, to eliminate isomorphic (partial) models, thus reducing the size of the search space. The correctness of the heuristic is proved. Some experimental data are given to show the performance and applications of the system.

参数化系统安全性的启发式符号验证

参数化系统(paramterized system)是指包含特定有限状态进程多个实例的并发系统,其中的参数是指系统内进程实例的数目,即系统的规模.反向可达性分析(backward reachability analysis)已被广泛用于验证参数化系统是否满足以向上封闭(upward-closed)集合表示的安全性(safety property).与有限状态系统验证相类似,参数化系统的验证同样也面临着状态爆炸(state explosion)问题,并且模型检测算法的有效性依赖于如何采用有效的数据结构表示状态集合.针对表示无穷状态的向上封闭集合,研究人员提出了多种基于约束(constraint-based)的符号表示方法.但这些方法依然面临着符号状态爆炸(symbolic state explosion)问题或者其包含判定问题,即判断一个约束条件集合符号化表示的实际状态集合是否为另一约束条件集合所对应的状态集合的子集,是Co-NP完全问题.因此,虽然有限状态验证技术能够验证一些具有一定规模的问题,但现有针对参数化系统的验证方法所能解决的问题的规模较为有限,需要近一步提高模型检测算法的效率.针对参数化系统提出了加快反向可达性分析的多个启发式规则,实验结果表明,这些启发式规则可以使算法的效率提高几个数量级,从而有助于解决现有参数化系统验证方法所存在的问题.

一种任务类型敏感的J2EE事务调度算法

J2EE(Java 2 platform enterprise edition)是构建分布式企业应用的基础中间件平台,当前的J2EE事务对资源的访问调度仍然是简单的先来先服务策略,导致服务器负载很重时,次要任务和关键任务争夺有限的资源,降低了关键任务的性能与成功率.为此,有必要识别任务类型,在资源不足时优先保证关键任务事务的执行.但提交给J2EE的事务基于交互方式执行,且缺乏必要的调度信息,因而不能简单地沿用已有的优先级驱动调度算法.提出一种新的事务调度算法TMPBP(threaded multi-queue priority-based protocol),该算法能够安全、有效地提高系统重负载情况下关键事务的服务质量,防止饥饿和优先级倒置.TMPBP包含了一种新的启发式优先级分派算法HRS(heuristic resource statistics),可以在调度信息缺乏的J2EE环境下动态识别关键事务.结果表明,通过合理地选择参数,TMPBP算法能够显著地提高关键事务的服务质量.

安达市碱性草地土壤颗粒的分维特征

运用土壤颗粒质量分形模型计算松嫩平原低平地安达试区植被分布区和碱斑区样点土壤颗粒的分形维数,并建立分形维数与土壤颗粒不同粒级间的回归关系,以探讨土地碱化后土壤粒径分布的分形特征及其与土壤物理性状的关系。结果表明:安达试区土壤颗粒分形维数较高,平均分别仅有48.7×10-5cm/s(Pit A)和4.30×10-6cm/s(Pit B),反映了该区土壤细颗粒含量高、土壤大孔隙数量少、土壤饱和导水率低的特征;土壤颗粒分形维数与黏粒含量呈对数正相关关系,而与粉粒和砂粒含量相关性不显著,说明在安达试区,影响土壤颗粒分形维数的主要因素是黏粒含量;羊草地土壤颗粒分形维数在土壤垂直剖面上的变异较大,说明植被生长促进了土壤质地的变异;碱斑地土壤颗粒分形维数明显大于羊草地,细颗粒含量高,饱和导水率低,说明碱斑的形成恶化了土壤物理性质;土壤颗粒分形维数可以反映安达市土壤物理性质的好坏,能作为土壤退化和生态环境恶化的评价指标。研究结果可为安达市以及松嫩平原盐碱地生态环境的修复和治理提供科学依据。

GPP问题的骨架分析与启发式算法设计

图的划分问题(GPP)是具有广泛应用背景的典型NP-难解问题,高效启发式算法一直是该领域的研究热点.作为设计启发式算法的有力工具,GPP的骨架分析存在理论分析结果匮乏、骨架规模过小等缺陷.文中采用构造偏移GPP实例的技巧,不仅在理论卜证明了获取GPP的骨架是NP-难解的,并且利用一般GPP实例与偏移实例的关系,实现了骨架规模的提高.在此基础上,文中对于目前求解GPP问题最好的算法之一的IBS进行了改进,提出了基于偏移实例的IBS算法(BI-IBS).算法BI-IBS首先构造偏移GPP实例,然后再利用局部最优解交集对它进行归约,最后再求解归约后的规模更小的新实例.实验结果表明,BI-IBS比现有算法在解的质量上有了较显著的提高.文中的工作较完善地解决了GPP的骨架研究存在的问题,所采用的构造偏移实例的技巧对于其它NP-难解问题的骨架理论分析及启发式算法设计亦具有较高的参考价值.

基于BDD的增量启发式搜索方法及其应用

增量启发式搜索是一种利用先前的搜索信息和启发信息提高本次搜索效率的方法，通常可用来解决动态环境下的重规划问题。在人工智能领域，一些实时系统常常需要根据外界环境的变化不断修正自身，这样就会产生一系列变化较小的相似问题，此时应用增量启发式搜索将会非常有效。另一方面，基于BDD的强大的搜索技术利用BDD有效操作性以及化简后唯一性的优点， 在一定程度上缓解了模型检测的状态爆炸问题，使得被检测状态的个数大大增加。 1、本文结合基于BDD的启发式搜索和基于BDD的增量搜索这两种方法给出了基于BDD的增量启发式搜索方法， 基于BDD的增量启发式搜索综合了基于BDD的搜索、增量搜索以及启发式搜索这三种方法的优点。它既用BDD作为数据结构以提高搜索的空间效率， 又结合了增量搜索的思想来提高重搜索的效率，同时，又引入了启发函数来进一步压缩搜索空间。 2、本文介绍了基于BDD的增量启发式搜索算法BDDRPA*并用大量的实验结果证明BDDRPA*的高效性。给定一个搜索问题， BDDRPA*算法先用基于BDD的启发式搜索方法搜出一条从初始节点到目标节点的最短路径；接着， 问题的状态格局发生改变，BDDRPA*再用基于BDD的增量搜索方法根据旧格局的迁移关系BDD_T构造出新格局的迁移关系BDD_{T'}， 然后再用启发式方法搜索路径，如此反复下去。 3、本文介绍了基于BDD的动态增量启发式搜索算法BDDD*并用大量的实验结果证明BDDD*的高效性。 BDDD*算法在机器人边走边扫描的过程中，不断根据机器人新获得的信息更新已知地图并重新规划路线。每次规划时，BDDD*都假设未知的领域没有任何障碍物， 也就是每个位置都是可通的，它按照这个假设去计算从当前位置到目标位置的最短路径。如果在行走的过程中扫描到了障碍物，它就把这条信息添加到它的地图中，然后重复 上面的过程，直到到达目标位置或者发现每条路径都被堵死为止。 BDDRPA*算法和BDDD*算法可以应用到机器人线路规划、智能交通及计算机网络的线路规划问题中。 另外，在机器学习和控制领域，也可以考虑使用BDDRPA*算法和BDDD*算法。

Discrete wavelets transform for signal denoising in capillary electrophoresis with electrochemiluminescence detection

Discrete wavelets transform (DWT). was applied to noise on removal capillary electrophoresis-electrochemiluminescence (CE-ECL) electropherograms. Several typical wavelet transforms, including Haar, Daublets, Coiflets, and Symmlets, were evaluated. Four types of determining threshold methods, fixed form threshold, rigorous Stein's unbiased estimate of risk (rigorous SURE), heuristic SURE and minimax, combined with hard and soft thresholding methods were compared. The denoising study on synthetic signals showed that wave Symmlet 4 with a level decomposition of 5 and the thresholding method of heuristic SURE-hard provide the optimum denoising strategy. Using this strategy, the noise on CE-ECL electropherograms could be removed adequately. Compared with the Savitzky-Golay and Fourier transform denoising methods, DWT is an efficient method for noise removal with a better preservation of the shape of peaks.

Molecular evidence for the sister relationship of the eastern Asia-North American intercontinental species pair in the Podophyllum group (Berberidaceae)

The presumed pair relationships of intercontinental vicariad species in the Podophyllum group (Sinopodophyllum hexandrum vs. Podophyllum pelatum and Diphylleia grayi vs. D. cymosa) were recently, considered to be paraphyletic. In the present paper, the trnL-F and ITS gene sequences of the representatives were used to examine the sister relationships of these two vicariad species. A heuristic parsimony analysis based on the trnLF data identified Diphylleia as the basal clade of the other three genera, but provided poor resolution of their inter-relationships. High sequence divergence was found in the ITS data. ITS1 region, more variable but parsimonyuninformative. has no phylogenetic value, Sequence divergence of the ITS2 region provided abundant, phylogenetically informative variable characters. Analysis of ITS2 sequences confirmeda sister relationship between the presumable vicariad species, in spite of a low bootstrap support for Sinopodophyllum hexandrum vs. Podophyllum pelatum. The combined ITS2 and trnL-F data enforced a sister relationship between Sinopodophyllum hexandrum and Podophyllum pelatum with an elevated bootstrap support of 100%. Based on molecular phylogeny, the morphological evolution of this group was discussed. The self-pollination might have evolved from cross-fertilization two times in this group. The different pollination and seed dispersal systems of Sinopodophyllum hexandrum and Podophlyllum pelatum resulted from their adaptations to different ecological habitats. The divergence time of Sinopodophyllum hexandrum-Podophyllum pelatum is estimated to be 6.52+/-1.89 myr based on the ITS divergence. The divergence of this species pair predated or co-occurred with the recent uplift of the Himalayas 4-3 myr during the late Miocene and the formation of the alpine habitats. Sinopodophyllum hexandrum developed a host of specialized characters in its subsequent adaptation to the arid alpine surroundings. The present study confirmed the different patterns of species relationship between Asian-North American disjuncts. The isolation of plant elements between North America and eastern Asia must have been a gradual process, resulting in the different phylogenetic patterns and divergence times of the disjuncts.

无线传感器网络中一种启发式最小连通支配集算法

针对最小连通配集问题设计了一种具有较高能量效率的启发式算法。算法首先把网络中所有的节点作为最小连通支配集的一个初始解,然后利用启发式修剪策略剔除冗余节点从而减小最小连通支配集的大小,直到没有冗余节点存在。文中将算法分成集中式和分布式两种情况进行了详细讨论。仿真结果表明,由于实现简便,该算法与其他已有算法相比较,在算法复杂性和算法稳定运行时间上有一定的优势。

基于粗糙集和多Agent系统的知识挖掘

通过优化知识表达系统中条件属性对决策属性的依赖度,深入研究了粗糙集并与多Agent系统相结合。利用离散粒子群算法,提出一种基于粒子群优化的粗糙集知识约简算法,该算法解决了启发式算法无法全局搜索进行约简的问题。最后通过在矿井中调度信息的应用验证了有效性。